#pragma once

#include<iostream>
#include<cassert>
#include<mutex>
#include<algorithm>
#include<sys/mman.h>
#include<unordered_map>
using std::cout;
using std::endl;


static const size_t NFREELISTS = 208;
static const size_t MAX_BYTES = 256 * 1024;
static const size_t PAGE_SHIFT = 13;
static const size_t NPAGES = 129;


//直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
	void* ptr = mmap(nullptr, kpage << 13, PROT_EXEC | PROT_READ | PROT_WRITE, MAP_SHARED, 0, 0);
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

// 获取内存对象的头4/8个字节的值, 即链接的下一个对象的地址
static void*& NextObj(void* obj)
{
    return (*(void**)obj);
}


// 管理切好的小块内存的自由链表
class FreeList
{
public:
    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

		_size += n;
    }

	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		start = _freeList;
		end = start;
		for(size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;

		_size -= n;
	}

    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

		_size++;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = NextObj(_freeList);

		_size--;

        return obj;
    }


    bool Empty()
    {
        return _freeList == nullptr;
    }

    size_t& MaxSize()
    {
        return _maxSize;
    }

	size_t Size()
	{
		return _size;
	}


private:
    void* _freeList = nullptr;
    size_t _maxSize = 1;
	size_t _size = 0;
};


// 通过指针长度判断系统位数
#if __SIZEOF_POINTER__==4 // 32位系统
    typedef size_t PAGE_ID;
#elif __SIZEOF_POINTER__==8 // 64位系统
    typedef unsigned long long PAGE_ID;
#endif

// span是管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0; // 页数

    Span* _prev = nullptr; //双向链表结构
    Span* _next = nullptr; 

    void* _freeList = nullptr; // 自由链表

	size_t _useCount = 0; // 该span分配给thread cache内存对象的个数

	bool _isUse = false; // 表征当前span是否正在被使用
};


// 双向链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	Span* PopFront()
	{
		assert(Begin());

		Span* span = Begin();
		Erase(Begin());

		return span;
	}

	void PushFront(Span* newSpan)
	{
		assert(newSpan);

		Insert(Begin(), newSpan);
	}

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }


    void Erase(Span* pos)
    {
        assert(pos);

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    bool Empty()
    {
        return _head->_next == _head;
    }

private:
    Span* _head = nullptr;

public:
    std::mutex _mtx;
};


// 计算对象大小的对齐和映射规则
class SizeClass
{
public:
    // 整体控制在最多10%左右的内碎片浪费
	// [1, 128]                          8byte对齐                          freeList[0, 16)
	// [128+1, 1024]                     16byte对齐                         freeList[16, 72)
	// [1024+1, 8*1024]                  128byte对齐                        freeList[72, 128)
	// [8*1024+1, 64*1024]               1024byte对齐                       freeList[128, 184)
	// [64*1024+1, 256*1024]             8*1024byte对齐                     freeList[184, 208)


	// 对齐大小的计算 - 对齐后给的字节数
	/*static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize = 0;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1) * alignNum;
		}
		else
		{
			alignSize = size;
		}

		return alignSize;
	}*/

	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			// 大于256KB的按页对齐
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
		return -1;
	}

    //计算映射到哪一个自由链表桶
	/*static inline size_t _Index(size_t bytes, size_t alignNum)
	{
		if (bytes % alignNum == 0)
		{
			return bytes / alignNum - 1;
		}
		else
		{
			return bytes / alignNum;
		}
	}*/

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };// 前四个区间桶的数量

		if (bytes <= 128)
		{
			// return _Index(bytes, 8);
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			// return _Index(bytes, 16) + group_array[0];
			return _Index(bytes, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			// return _Index(bytes, 128) + group_array[0] + group_array[1];
			return _Index(bytes, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			// return _Index(bytes, 1024) + group_array[0] + group_array[1] + group_array[2];
			return _Index(bytes, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			// return _Index(bytes, 8 * 1024) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
			return _Index(bytes, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}

    // 一次从central cache中批量申请多少个内存对象
    static size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = MAX_BYTES / size;

        if(num < 2)
            num = 2;

        if(num > 512)
            num = 512;

        return num;
    }

	// 一次从page cache中获取多少个页
	static size_t NumMovePage(size_t size)
	{
		assert(size <= MAX_BYTES);

		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;

		if(npage < 1)
			npage = 1;

		return npage;
	}
};